// LeetCode 75 颜色分类 原题

// 题目描述
// 【红白蓝彩条排序】
// 问题描述: 给你一个仅有红，白，蓝三种颜色组成的10个条块序列，现需要你将这些条块按照红，白，蓝的顺序排好，可用1代表红色，2代表白色，3代 表蓝色，要求时间复杂度为O(n)。例如，给定彩色条块序列为： 
// ｛蓝、白、红、白、蓝、红、白、白、红、蓝｝ 
// 则要求排列结果为： 
// ｛红、红、红、白、白、白、白、蓝、蓝、蓝｝ 

// 输入描述: 
// 1
// ｛蓝、白、红、白、蓝、红、白、白、红、蓝｝ 
// 输出描述: 
// 1
// ｛红、红、红、白、白、白、白、蓝、蓝、蓝｝
//  输入样例: 
// 复制代码
// 1
// 3 2 1 2 3 1 2 2 1 3 
// 输出样例: 
// 1
// 1 1 1 2 2 2 2 3 3 3

void solve(vector<int>& nums) {
	int l = 0, r = nums.size() - 1;

	for(int i = 0; i < r; ++i) {
		while(i <= r && nums[i] == 3) {
			swap(nums[i], nums[r]);
			r--;
		}

		if(nums[i] == 1) {
			swap(nums[l], nums[i]);
			l++;
		}
	}
}